package com.lfg.leetcode.leetcode0;


public class No44IsMatch {

    public static void main(String[] args) {
        boolean ret = isMatch("abaabaaaabbabbaaabaabababbaabaabbabaaaaabababbababaabbabaabbbbaabbbbbbbabaaabbaaaaabbaabbbaaaaabbbabb", "ab*aaba**abbaaaa**b*b****aa***a*b**ba*a**ba*baaa*b*ab*");
        System.out.println(ret);
    }

    public static boolean isMatch(String s, String p) {
        if (null == s && null == p) {
            return true;
        }
        if (null == s || null == p) {
            return false;
        }
        if (s.equals(p)) {
            return true;
        }
        if ("".equals(p)) {
            return false;
        }
        StringBuilder sb = new StringBuilder();
        if (p.length() > 0) {
            sb.append(p.charAt(0));
        }
        for (int i = 1; i < p.length(); i++) {
            if (p.charAt(i) == p.charAt(i - 1) && p.charAt(i - 1) == '*') {
                continue;
            }
            sb.append(p.charAt(i));
        }
        Boolean[][] dp = new Boolean[s.length()][p.length()];
        return isMatch(s, s.length() - 1, sb.toString(), sb.length() - 1, dp);
    }


    public static boolean isMatch(String s, int si, String p, int pi, Boolean[][] dp) {
        if (si < 0 && pi < 0) {
            return true;
        }
        if (si < 0 && p.charAt(pi) == '*') {
            boolean r = false;
            Boolean b = dp[si - 1][pi];
            if (b == null && (r = isMatch(s, si - 1, p, pi, dp))) {
                dp[si - 1][pi] = r;
            }
            return r;
        }
        if (si < 0 || pi < 0) {
            return false;
        }
        if (p.charAt(pi) == '*') {
            if (pi > 0 && (p.charAt(pi - 1) == '*' || p.charAt(pi - 1) == '?' || p.charAt(pi - 1) == s.charAt(si))) {
                Boolean b = dp[si][pi - 1];
                boolean r = false;
                if (b == null && (r = isMatch(s, si, p, pi - 1, dp))) {
                    dp[si][pi - 1] = r;
                }
                if (r) {
                    return r;
                }
            }
            boolean r = false;
            Boolean b = dp[si - 1][pi];
            if (b == null && (r = isMatch(s, si - 1, p, pi, dp))) {
                dp[si - 1][pi] = r;
            }
            return r;
        }
        if (p.charAt(pi) == '?' || p.charAt(pi) == s.charAt(si)) {
            boolean r = false;
            Boolean b = dp[si - 1][pi - 1];
            if (b == null && (r = isMatch(s, si - 1, p, pi - 1, dp))) {
                dp[si - 1][pi - 1] = r;
            }
            return r;
        }
        return false;
    }
}

